//
//  BinaryTreeNode.swift
//  BinaryTree
//
//  Created by 郭红旗 on 2021/11/10.
//

import UIKit

class BinarySearchTree<T:Equatable>{
    typealias comparatorClosure = (_ e1:T,_ e2:T) -> Int
    private var size:Int = 0
    var root:Node<T>?
    private var comparator:comparatorClosure?
    /// 比较器
    init(comparator:@escaping comparatorClosure) {
        self.comparator = comparator
    }
    /// 根节点
    public func getRoot() -> Node<T>?{
        return root
    }
    /// 是否为空
    public func getSize() -> Int{
        return size
    }
    /// 是否为空
    public func isEmpty() -> Bool{
        return false
    }
    /// 清理
    public func clear(){
    }
    /// 添加
    public func add(element:T?){
        guard let el = element else {
            return
        }
        // 添加根节点
        if root == nil {
//            root = Node.init(element: el, parent: nil)
            root = createBinaryTree(element: el, parent: nil)
            size += 1
            afterAdd(root!)
            return
        }
        // 添加的不是第一个节点。找到父节点
        var node = root
        var parent:Node<T>? = nil
        var cmp = 0
        while node != nil {
            cmp = compare(e1: el, e2: node!.element)
            parent = node
            if cmp > 0 {
                node = node?.right
            }else if cmp < 0{
                node = node?.left
            }else{
                return
            }
        }
        // 判断插入到父节点的哪个位置
//        let newNode = Node.init(element: el, parent: parent)
        let newNode = createBinaryTree(element: el, parent: parent)

        if cmp > 0 {
            parent?.right = newNode
        }else{
            parent?.left = newNode
        }
        size += 1
        afterAdd(newNode)
        
    }
    
    open func afterAdd(_ node:Node<T>){
       
    }
    open func afterRemove(_ node:Node<T>){
       
    }
    /// 移除
    public func remove(element:T){
        guard let node = node(withElement: element) else {
            return
        }
        removeNode(node: node)
    }
    func removeNode(node:Node<T>) {
        var tree = node
        if tree.hasTwoChild() { // 度为2的节点
            // 找到后继节点
            let s = successor(node: tree)
            tree.element = s.element
            tree = s
        }
        // 删除tree （tree的度必然为1或0）
        let replace = tree.left != nil ? tree.left : tree.right
        if replace != nil { // 度为1的节点
            // 更该parent
            replace?.parent = tree.parent
            if tree.parent == nil { // tree是度为1的节点并且是根节点
                root = replace
            }else if(tree.element == tree.parent?.left?.element){
                tree.parent?.left = replace
            }else{
                tree.parent?.right = replace
            }
            // 删除节点之后处理
            afterRemove(tree)
        }else if (tree.parent == nil){ // tree是叶子节点并且是根节点 且度为0
            root = nil
            // 删除节点之后处理
            afterRemove(tree)
        }else{ // tree 是叶子节点但不是根节点  且度为0
            if tree.element == tree.parent!.right?.element {
                tree.parent?.right =  nil
            }else{
                tree.parent?.left = nil
            }
            // 删除节点之后处理
            afterRemove(tree)
        }
        
    }
    /// 找前驱节点
    func predecssor(node:Node<T>) -> Node<T> {
        var tree = node.left
        var result = tree
        while tree != nil {
            result = tree
            tree = tree?.right
        }
        return result!
    }
    /// 找后继节点
    func successor(node:Node<T>) -> Node<T> {
        var tree = node.right
        var result = tree
        while tree != nil {
            result = tree
            tree = tree?.left
        }
        return result!
    }
    /// 根据元素获取节点
    func node(withElement el:T) -> Node<T>? {
        var node = root
        while node != nil {
            let result = comparator?(el,node!.element)
            if result == 0 {
                return node
            }else if result! > 0{
                node = node?.right
            }else{
                node = node?.left
            }
        }
        return nil
    }
    /// 包含
    public func contains(element:T) -> Bool{
        return false
    }

    open func createBinaryTree(element: T, parent: Node<T>?) -> Node<T> {
        return Node.init(element: element, parent: parent)
    }
    
    // MARK: - PRIVATEMETHODS
    
    /// - Parameters:
    ///   - e1: 目标1
    ///   - e2 : 目标2
    /// - Parameter e1: 目标1
    /// - Parameter e2 : 目标2
    /// - Returns : 返回值 0:值相等    大于0：e1大于e2    小于0：e1小于e2
    private func compare(e1:T,e2:T) -> Int{
        return comparator?(e1,e2) ?? 0
    }
    
    enum VendingMachineError: Error {
        case invalidSelection
        case insufficientFunds(coinsNeeded: Int)
        case outOfStock
    }

    
    class Node<E:Equatable>:Equatable{
        static func == (lhs: BinarySearchTree<T>.Node<E>, rhs: BinarySearchTree<T>.Node<E>) -> Bool {
            return lhs.element == rhs.element
        }
        
        var element:E
        var left:Node<E>?
        var right:Node<E>?
        var parent:Node<E>?
        
        init(element:E,parent:Node<E>?){
            self.element = element
            self.parent = parent
        }
        
        var asString:String { return treeString(self){("\($0.element)",$0.left,$0.right)}  }

        func isLeftChild() -> Bool {
            return parent != nil && self == parent?.left
        }
        
        func isRightChild() -> Bool {
            return parent != nil && self == parent?.right
        }
        func hasTwoChild() -> Bool {
            return left != nil && right != nil
        }
    }
    
  

}

extension BinarySearchTree{
    // MARK: - 前序遍历
    /// 递归遍历
    public func qianxuRecursion(node:Node<T>?,printBlock:(T)->Void){
        guard let tree = node else {
            return
        }
        printBlock(tree.element)
        qianxuRecursion(node: tree.left, printBlock: printBlock)
        qianxuRecursion(node: tree.right, printBlock: printBlock)
    }
    /// 非递归遍历
    public func preorderSTraversal(node:inout Node<T>?){
//        var res = [T?]()
        var stack = [Node<T>?]()
        while node != nil || stack.count > 0 {
            if node != nil {
//                res.append(node?.element)
                print(node?.element)
                stack.append(node)
                node = node?.left
            }else{
                guard let lastNode = stack.last as? Node<T> else {
                    continue
                }
                node = lastNode.right
                stack.removeLast()
            }
        }
    }
    
    // MARK: - 中序遍历
    public func zhongxuRecursion(node:Node<T>?,printBlock:(T)->Void){
        guard let tree = node else {
            return
        }
        qianxuRecursion(node: tree.left, printBlock: printBlock)
        printBlock(tree.element)
        qianxuRecursion(node: tree.right, printBlock: printBlock)
    }
}
